package day_2022_4_to_7.nowcoder;

/**
 * 反转链表
 * @author haomin
 * @date 2022/04/15 16:42
 **/
public class ReverseList_12f {
    public class Solution {
        // 头插1（new 新节点）
        public ListNode ReverseList1(ListNode head) {
            if(head==null|| head.next==null){
                return head;
            }
            ListNode dummyHead = new ListNode(-1);
            while(head != null){
                // 创建一个节点存当前head的值
                ListNode cur = new ListNode(head.val);
                // 头插
                cur.next = dummyHead.next;
                dummyHead.next = cur;

                head = head.next;
            }
            return dummyHead.next;
        }

        // 头插2（不用new 空间复杂度O1）
        public ListNode ReverseList1_2(ListNode head) {
            if(head==null|| head.next==null){
                return head;
            }
            ListNode newNode = null;
            while(head != null){
                ListNode pre = head;
                head = head.next;

                //再将p标识的节点头查到新链表
                pre.next = newNode;
                newNode = pre;
            }
            return newNode;
        }

        // 原地移动（双指针）和 头插2类似
        public ListNode ReverseList2(ListNode head) {
            if(head == null || head.next == null){
                return head;
            }

            ListNode prev = null;
            // 当前需要处理的节点(需要反转)
            ListNode cur = head;
            while (cur != null){
                // 存储cur之后的链
                ListNode node = cur.next;
                // 原地移动，（改变next指向）
                cur.next = prev;
                prev = cur;

                cur = node;
            }
            return prev;
        }

        // 原地移动（三指针）
        public ListNode ReverseList3(ListNode head) {
            if(head == null || head.next == null){
                return head;
            }

            ListNode left = head;
            ListNode mid = left.next;
            ListNode right = mid.next;
            // 反转中间节点，但是当right 为 null时，最后一个节点没有处理
            while (right != null){
                mid.next = left;

                left = mid;
                mid = right;
                right = right.next;
            }
            // 处理最后一个节点 || 当链表只有两个节点时
            mid.next = left;
            head.next = null;

            return mid;
        }

        // 递归写法
        public ListNode ReverseList4(ListNode head) {
            if(head == null || head.next == null){
                return head;
            }

            ListNode second = head.next;
            // 反转第二个节点之后的子链表
            ListNode newHead = ReverseList4(head.next);

            // 反转链表（每次递归都只是处理second节点前后指向）
            second.next = head;
            head.next = null;
            return newHead;
        }
    }
}